# 给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
#  注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
#  返回一个表示每个字符串片段的长度的列表。
#
#
# 示例 1：
# 输入：s = "ababcbacadefegdehijhklij"
# 输出：[9,7,8]
# 解释：
# 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
# 每个字母最多出现在一个片段中。
# 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
#
#  示例 2：
# 输入：s = "eccbbbbdec"
# 输出：[10]
#
#
#  Related Topics 贪心 哈希表 双指针 字符串 👍 1123 👎 0
from typing import List, Dict


class Solution:
    def partitionLabels1(self, s: str) -> List[int]:
        last, partitions = [0] * 26, []
        # 先记录每个字母的最后下标位置
        for i, ch in enumerate(s):
            last[ord(ch) - ord('a')] = i
        start = end = 0
        # 贪心计算每个段的位置
        for i, ch in enumerate(s):
            end = max(end, last[ord(ch) - ord("a")])
            if i == end:
                partitions.append(end - start + 1)
                start = end + 1
        return partitions

    def partitionLabels(self, s: str) -> List[int]:
        return self.partitionLabels1(s)


if __name__ == "__main__":
    s = "ababcbacadefegdehijhklij"

    map = {'1': 1, '2': 3}
    print(map.values())
    print(map.get(s, 'xxxx'))
    l = List[str]()
    mp = Dict[str, List[str]]()  # key: 每个字符个数的 tuple26 value: 对应的字符 list
    print(Solution().partitionLabels(s))
